Valid tic-tac-toe state

Time: O(1); Space: O(1); medium

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters ” “,”X“,and”O“. The” ” character represents an empty square.

Here are the rules of Tic-Tac-Toe: * Players take turns placing characters into empty squares (’ ‘). * The first player always places ’X’ characters, while the second player always places ‘O’ characters. * ‘X’ and ‘O’ characters are always placed into empty squares, never filled ones. * The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal. * The game also ends if all squares are non-empty. * No more moves can be played if the game is over.

Example 1:

Input: board = [‘O’, ’ ‘,’ ’]

Output: False

Explanation:

  • The first player always plays ‘X’

Example 2:

Input: board = [‘XOX’, ’ X ‘,’ ’]

Output: False

Explanation:

  • Players take turns making moves.

Example 3:

Input: board = [‘XXX’, ’ ‘, ’OOO’]

Output: False

Example 4:

Input: board = [‘XOX’, ‘O O’, ‘XOX’]

Output: True

Notes:

  • board is a length-3 array of strings, where each string board[i] has length 3.

  • Each board[i][j] is a character in the set {’ ‘, ’X’, ‘O’}.

[4]:

class Solution1(object):
    def validTicTacToe(self, board):
        """
        :type board: List[str]
        :rtype: bool
        """
        def win(board, player):
            for i in range(3):
                if all(board[i][j] == player for j in range(3)):
                    return True
                if all(board[j][i] == player for j in range(3)):
                    return True

            return (player == board[1][1] == board[0][0] == board[2][2] or \
                    player == board[1][1] == board[0][2] == board[2][0])

        FIRST, SECOND = ('X', 'O')

        x_count = sum(row.count(FIRST) for row in board)
        o_count = sum(row.count(SECOND) for row in board)

        if o_count not in {x_count-1, x_count}:
            return False
        if win(board, FIRST) and x_count-1 != o_count:
            return False
        if win(board, SECOND) and x_count != o_count:
            return False

        return True

[5]:

s = Solution1()

board = ['O ', ' ', ' ']
assert s.validTicTacToe(board) == False

board = ['XOX', ' X ', ' ']
assert s.validTicTacToe(board) == False

board = ['XXX', ' ', 'OOO']
assert s.validTicTacToe(board) == False

board = ['XOX', 'O O', 'XOX']
assert s.validTicTacToe(board) == True